package com.leetcode.partition10;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/9/25 9:22
 */
public class LC931下降路径最小和 {

    public static int minFallingPathSum(int[][] matrix) {
        return dynamicProgramming(matrix);
    }

    public static void main(String[] args) {
//        int[][] matrix = {
//                {2, 1, 3},
//                {6, 5, 4},
//                {7, 8, 9}
//        };
        int[][] matrix = {{-48}};
        System.out.println(minFallingPathSum(matrix));
    }

    private static int dynamicProgramming(int[][] matrix) {
        int[][] dp = new int[matrix.length][matrix[0].length];
        for (int j = 0; j < matrix[0].length; j++) dp[0][j] = matrix[0][j];
        int answer = Integer.MAX_VALUE;
        for (int i = 1; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (j - 1 >= 0 && j + 1 < matrix[0].length) {   //两个边界都合理的情况
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i - 1][j - 1]), dp[i - 1][j + 1]) + matrix[i][j];
                } else if (j - 1 < 0 && j + 1 < matrix[0].length) { //左上方越界
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j + 1]) + matrix[i][j];
                } else if (j - 1 >= 0 && j + 1 >= matrix[0].length) {   //右上方越界
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1]) + matrix[i][j];
                } else {
                    dp[i][j] = dp[i - 1][j] + matrix[i][j];     //只有一列的情况，下一层只能使用上一层的状态
                }
            }
        }
        for (int j = 0; j < matrix[0].length; j++) answer = Math.min(answer, dp[matrix.length - 1][j]);
        Arrays.stream(dp).forEach(val -> System.out.println(Arrays.toString(val)));
        return answer;
    }
}
